1. Field of the Invention
The present invention relates to an apparatus for performing a modular multiplication. More particularly, it relates to an apparatus for performing a modular multiplication using 2N, twice a modular N.
2. Discussion of Related Art
In recent years, remarkable research and development have been devoted to a high-speed modular multiplication in a cryptographic scheme for protecting the content of data. Particularly, a cryptography is much more enforced by using a modular exponentiation against the development of the cryptanalysis system. The modular exponentiation can be performed by repeating modular multiplications, and the speed at the modular multiplication is performed plays an important part in the processing speed of the overall cryptographic algorithm. Accordingly, a high-speed cryptographic scheme is becoming necessary with the tendency of enhancing the processing speed of the modular multiplication. In the modular multiplication, two integers are multiplied and its result is divided by another integer to obtain the residue. According to a conventional modular multiplication, a partial product of a multiplicand as to each word of a multiplier is divided to obtain a residue, or the last word is removed whenever a residue is obtained.
A complicated divider or a modular inverse-multiplier utilizing Euclid algorithm is used in the conventional modular multiplication to get a proper quotient, so there is a limit in enhancement of the processing speed. This makes it difficult to perform the real-time processing to a large-capacity key cryptographic algorithm.